# 剑指Offer题解 - Day47

# 剑指 Offer 15. 二进制中 1 的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

1
2
3

提示：

输入必须是长度为 32 的 二进制串 。

思路：

在JavaScript中，可以通过n.toString(2) 的方式，将十进制的数字n转换为二进制。本题中给出，输入是二进制串，因此无需再进行转换。

首先考虑将二进制串转换为字符串，然后遍历字符串统计1出现的次数并返回。

# 暴力法

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    for (const s of (+n.toString(10)).toString(2)) {
        if (s === '1') count++;
    }
    return count;
};

1
2
3
4
5
6
7
8
9
10
11

时间复杂度 O(1)。
空间复杂度 O(1)。

分析：

由于将二进制串直接转换为字符串会默认转换为十进制，因此这里首先转换为十进制的数字后，再转换为二进制组成的字符串。

然后遍历字符串统计1出现的次数并返回。

遍历次数是32次，因此是常数级别的时间复杂度。声明count变量仅占用常数级别的空间。

# 位运算

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    while(n) {
        n &= (n - 1)
        count++;
    }
    return count;
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度 O(m)。
空间复杂度 O(1)。

分析：

核心操作是位运算 n & (n - 1) 。每执行一次该位运算，可以消除最右边的1。原理如下：

n - 1解析：二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
n & (n - 1)解析：二进制数字 n 最右边的 1 变成 0 ，其余不变。

因此循环处理，每消除一个 1 就对最终计数器累加。直到 n 为 0 为止。最终返回计数器即可。

时间复杂度取决于二进制串当中有多少个 1 。声明count变量仅占用常数级别的空间。

# 总结

本题考查位运算。因此暴力法的字符串遍历方法不建议面试的时候使用。位运算有很多实用的小技巧，比较常用的要牢记于心。

剑指Offer题解 - Day46 剑指Offer题解 - Day48